package com.cheng.learn.sort;

/**
 * @description: 归并排序
 * @author: ChengHaiZhu
 * @create: 2021-03-19 00:21
 **/
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 , 23};
        mergeSort(arr,0, arr.length - 1,new int[arr.length]);
        System.out.println("排序后:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    /**
     * 归并算法,采用迭代方式先将左右子序列归并，再合并两个子序列
     */
    public static void mergeSort(int[] arr, int low, int high ,int[] temp){
        if(low < high){
            int mid = (low + high)/2;
            mergeSort(arr,low,mid,temp);
            mergeSort(arr,mid+1,high,temp);
            // 合并的时候通过low mid high值来确认两个子序列
            merge(arr,low,mid,high,temp);
        }
    }

    /**
     *  合并两个有序序列,将low 到 high合并排序好，然后替换原数据数据
     */
    public static void merge(int[] arr,int low, int mid,int high,int[] temp){
        int i = 0;
        int j = low;
        int k = mid + 1;
        while(j <= mid && k <= high){
            // 从小到大排序，所以先放小的
            if(arr[j] > arr[k]){
                temp[i++] = arr[k++];
            }else{
                temp[i++] = arr[j++];
            }
        }
        // 若左边序列还有剩余，就都放进临时数组
        while(j <= mid){
            temp[i++] = arr[j++];
        }
        // 若右边序列还有剩余，就都放进临时数组
        while(k <= high){
            temp[i++] = arr[k++];
        }
        // 最后将temp数组排序的内容赋值进arr
        for(int t=0;t<i;t++){
            arr[low+t] = temp[t];
        }
    }
}
